package org.ala.linshen.dp;

/**
 * 一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
 *
 * 现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
 *
 * 注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 1
 * 输出：4
 * 解释：
 * 可能的放置方式：
 * 1. 所有地块都不放置房子。
 * 2. 一所房子放在街道的某一侧。
 * 3. 一所房子放在街道的另一侧。
 * 4. 放置两所房子，街道两侧各放置一所。
 * 示例 2：
 *
 *
 * 输入：n = 2
 * 输出：9
 * 解释：如上图所示，共有 9 种可能的放置方式。
 *
 * @author ala
 * @data 2024-09-14 09:13
 */
public class Q2320 {

    public static void main(String[] args) {
        Q2320 q = new Q2320();

        int n = 1000;

        System.out.println(q.countHousePlacements(n));
    }


    /**
     *  1）因为两行之间没有互相影响，所以是相互独立的，所以答案 = 第一行的方案数 * 第二行的方案数
     *  2）考虑单行，dp[i]表示该行第i列的方案数：
     *      第i列如果不放，则第i - 1列的放置数能取满
     *      第i列如果放，则第i - 1列的放置数能取满
     *      dp[i] = dp[i - 1] + dp[i - 2]
     *      dp[0] = 1, dp[1] = 2
     *  3）最后答案 = dp[i]²
     */
    public int countHousePlacements(int n) {
        return (int)((dp[n] % MOD * dp[n] % MOD) % MOD);
    }
    static int MOD = (int)1e9 + 7;
    static long[] dp;
    static {
        dp = new long[10001];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2 ; i < dp.length ; i++) {
            dp[i] = (dp[i - 1] % MOD + dp[i - 2] % MOD) % MOD;
        }
    }
}
